use std::{
    fs::File,
    io::{self, Read},
    time::Instant,
};

struct MaxFactor {
    max_factor: u128,
}

fn abs_sub(a: u128, b: u128) -> u128 {
    if a > b {
        a - b
    } else {
        b - a
    }
}
fn gcd(a: u128, b: u128) -> u128 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn bmul(mut a: u128, mut b: u128, m: u128) -> u128 {
    // 快速乘
    a %= m;
    let mut res = 0;
    while b > 0 {
        if (b & 1) == 1 {
            res = (res + a) % m;
        }
        a = (a << 1) % m;
        b >>= 1;
    }
    res
}

fn qpow(mut x: u128, mut p: u128, m: u128) -> u128 {
    // 快速幂
    let mut ans = 1;
    while p != 0 {
        if (p & 1) == 1 {
            ans = bmul(ans, x, m);
        }
        x = bmul(x, x, m);
        p >>= 1;
    }
    ans
}

fn rand_from_file() -> io::Result<u128> {
    let mut file = File::open("/dev/random")?;
    let mut buf = [0u8; 16];
    file.read_exact(&mut buf)?;
    Ok(u128::from_ne_bytes(buf))
}

fn rand() -> u128 {
    if let Ok(res) = rand_from_file() {
        res
    } else {
        let t = Instant::now();
        t.elapsed().as_nanos()
    }
}

fn miller_rabin(p: u128) -> bool {
    // 判断素数
    if p < 2 {
        return false;
    }
    if p == 2 {
        return true;
    }
    if p == 3 {
        return true;
    }
    let mut d = p - 1;
    let mut r = 0;
    while (d & 1) == 0 {
        r += 1;
        d >>= 1; // 将d处理为奇数
    }
    for _ in 0..10 {
        let a = rand() % (p - 2) + 2;
        let mut x = qpow(a, d, p);
        if x == 1 || x == p - 1 {
            continue;
        }
        for _ in 0..r {
            x = bmul(x, x, p);
            if x == p - 1 {
                break;
            }
        }
        if x != p - 1 {
            return false;
        }
    }
    true
}

fn pollard_rho(x: u128) -> u128 {
    let mut s = 0;
    let mut t = 0;
    let c = rand() % (x - 1) + 1;
    let mut goal = 1;
    let mut val = 1;
    loop {
        for step in 1..=goal {
            t = (bmul(t, t, x) + c) % x;
            val = bmul(val, abs_sub(t, s), x);
            if (step % 127) == 0 {
                let d = gcd(val, x);
                if d > 1 {
                    return d;
                }
            }
        }

        let d = gcd(val, x);
        if d > 1 {
            return d;
        }
        goal *= 2;
        s = t;
        val = 1;
    }
}

impl MaxFactor {
    fn new() -> Self {
        MaxFactor { max_factor: 0 }
    }
    fn fac(&mut self, mut x: u128) {
        if x <= self.max_factor || x < 2 {
            return;
        }
        if miller_rabin(x) {
            if self.max_factor < x {
                self.max_factor = x;
            }
            return;
        }
        let mut p = x;
        while p >= x {
            p = pollard_rho(x);
        }
        while (x % p) == 0 {
            x /= p;
        }
        self.fac(x);
        self.fac(p);
    }
}

pub fn find_max_prime_factor(number: u128) -> u128 {
    let mut max_factor = MaxFactor::new();
    max_factor.fac(number);
    max_factor.max_factor
}
